1. Field of the Invention
The present invention relates to a system and method for geometric modeling where incremental changes to the model can be efficiently made and conceptualized. In particular, the method of the present invention provides a graph-based solution technique to present and manipulate a constraint driven geometric model and develops an ordered list of dependencies among geometric entities to serve as an execution sequence when changing the model.
2. Description of Problem the and Related Art
Geometric modeling of a system is important in many fields. An important subclass of geometric modeling problems are constraint driven problems where the positions, orientations, and dimensions of the geometric entities in the model should satisfy a set of constraints. Examples include: describing mechanical assemblies; constraint based sketching and design; geometric modeling for CAD; and kinematic analysis of robots and other mechanisms.
Current Computer-Aided Design (CAD) systems are generally limited to activities that occur at the end of the design cycle. However, some studies have shown that 75% of the cost of product development is determined before current CAD systems become useful, e.g. during the product "concept" stage. Therefore, there is a need for computer-aided design tools which are useful in making the critical decisions at the beginning of the design cycle--i.e. "conceptual design." Such tools would be very useful in the early design stages to manipulate the geometric entities in the model while satisfying the constraints imposed on the model. Additionally, such tools would be very useful for animation, tolerance determination, design sensitivity, and other activities later in the design cycle.
Current approaches for handling constrained geometric models have a number of disadvantages. Conventional approaches usually model the geometry and constraints with algebraic equations (usually non-linear equations) that relate the configuration variables of the different geometric entities according to the constraints. The equations are then solved either numerically or symbolically to yield the desired configuration for geometric entities. After developing this system of algebraic equations an iterative solution technique is usually used, e.g. Newton-Raphson, to evaluate the values of the variables representing the geometric entities.
Such iterative solution techniques have many drawbacks. The principle problem is that iterative techniques slow the solution time dramatically as a function of problem complexity. Iterative solution time is related to a cube function of the number of constraints--O(c.sup.3). Additionally, over constrained situations are common and require pre and post analysis to remove redundant constraints before solving to check them for consistency. Newton-Raphson iterative techniques can jump chaotically between different roots of the error function during solution of the algebraic equations. Further, under constrained situations require pseudoinverse techniques since the constraint matrix is not square.
I. E. Sutherland, SKETCHPAD, a Manpk -Machine Graphical Communication System, PhD thesis, Massachusetts Institute of Technology, Cambridge, Mass., 1963 and V. C. Lin. Variational geometry in computer-aided design. Master's thesis, Massachusetts Institute of Technology, May 1981 (incorporated for Background) illustrate current research approaches to convert geometric constraints into algebraic equations, generally nonlinear, and use iterative techniques, such as Newton-Raphson to evaluate equations.
H. O. Peitgen and P. H. Richter, The Beauty of Fractals: Images of Complex Dynamical Systems, Springer-Verlag, Berlin, 1986 and William H. Press, Brian P. Flannery, Saul A. Teukolsky, and William T. Vetterling, Numerical Recipes: The Art of Scientific Computing, Cambridge University Press, Cambridge, U.K. 1986 (incorporated for Background) describe iterative solution techniques (e.g. Newton-Raphson) for systems of non-linear algebraic equations, particularly ones that present constraints using error terms which vanish when the constraint is satisfied.
Another approach is to use symbolic solutions to rewrite the algebraic equations and isolate the configuration variables in the equations in a serial fashion. However, symbolic techniques are feasible and complete only for very small problems because the time required to find a solution is excessive.
B. Buchberger, G. E. Collins, and R. Loos, editors, Computer Algebra; Symbolic and Algebraic Computation, Springer-Verlag, Wein, second edition, 1983 (incorporated for Background) is illustrative of symbolic solutions which rewrite algebraic rules to isolate the configuration variables in the equations defining the geometric model.
G. L. Jr. Steele, The Definition and Implementation of a Computer Programming Language Based on Constraints, PhD thesis, Massachusetts Institute of Technology, Cambridge, Mass., 1980; A. Borning, THINGLAB-A Constraint Oriented Simulation Laboratory PhD thesis, Stanford University, Palo Alto, Calif., 1979; and J. Gosling, Algebraic Constraints, PhD thesis, Carnegie-Mellon University, Pittsburgh, Pa., 1983 (incorporated for Background) use constraint propagation schemes (mostly local propagation) to handle the constraint driven model problem. While these references hold some potential for providing nice interactive environments for simple parametric geometry problems, they do not scale well to complex models.
Some commercial products are available that are either limited in coverage or not very robust. TCM's product "D.sup.3," is useful for drafting board geometry problems. "Pro Engineer" from Parametric Technology Corporation is useful for fully constrained geometric problems. "Premise," a product from Design View, uses a variational approach, which while versatile, is not robust.